package com.gaogzhen.algorithms4.sort;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

/**
 * 插入排序
 * 思想：希尔排序的思想是使任意间隔h的元素都是有序的。这样的数组被称为h有序数组。
 * 算法：
 * 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 * 按增量序列个数k，对序列进行k 趟排序；
 * 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 */
public class Shell {

    /**
     * 排序方法
     * @param a     实现了Comparable接口的待排序数组
     */
    public static void sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        // 递增序列1, 4, 13, 40, ...
        while (h < N / 3) h = 3 * h + 1;
        while (h >=  1) {
            // 将数组变为h有序
            for (int i = h; i < N; i++) {
                // 把a[i]插入子数组a[i-h],a[i-2*h],a[i-3*h],...中
                int preIndex = i - h;
                while (preIndex >= 0 && less(a[i], a[preIndex])) {
                    // a[i]如果比子数组中的其他项小，想要的项后移一位
                    a[preIndex + h] = a[preIndex];
                    preIndex -= h;
                }
                // 把a[i]插入子数组a[i-h],a[i-2*h],a[i-3*h],...合适位置
                exch(a, preIndex + h, i);
            }
            h /= 3;
        }

    }

    /**
     * 比较大小
     * @param a     目标a
     * @param b     目标b
     * @return      返回布尔值
     */
    private static  boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    /**
     * 交换数组元素
     * @param a     数组
     * @param i     索引
     * @param j     索引
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 打印数组
     * @param a     数组
     */
    private static void show(Comparable[] a) {
        // 单行打印数组
        for (int i = 0; i < a.length; i++) {
            StdOut.print(a[i] + " ");
        }
        StdOut.println();
    }

    /**
     * 测试数组是否已经有序
     * @param a     带测试数组
     * @return      测试结果: true-数组有序；false-数组无序
     */
    public static boolean isSorted(Comparable[] a) {
        // 测试数组是否已经有序
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i-1])) return false;
        }
        return  true;
    }

    public static void main(String[] args) {
        // 从标准输入读取字符串，将他们排序并输出
        String[] a = StdIn.readAllStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}
